<?php
/**
 * Copyright 2011  SURFfoundation
 * 
 * This file is part of ESCAPE.
 * 
 * ESCAPE is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * ESCAPE is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with ESCAPE.  If not, see <http://www.gnu.org/licenses/>.
 * 
 * For more information:
 * http://escapesurf.wordpress.com/
 * http://www.surffoundation.nl/
 * 
 * Contact: d.vierkant@utwente.nl
 * 
 * @license http://www.gnu.org/licenses/gpl.html GNU GPLv3
 */
?>
<?php
/**
 * Levenshtein comparator
 * 
 * Compares to entities using the levenshtein algoritm. The total result score is the average of the lowest matching score for each property value.
 */
class entityresolution_comparator_Levenshtein implements entityresolution_Comparator
{
	/**
	 * Predicate weights.
	 * @var array[string]float
	 */
	protected $predicateWeights;
	
	/**
	 * Character insertion cost. 
	 * @var int
	 */
	protected $costIns;
	
	/**
	 * Character replacement cost. 
	 * @var int
	 */
	protected $costRep;
	
	/**
	 * Character deletion cost. 
	 * @var int
	 */
	protected $costDel;
	
	/**
	 * Create a new comparator instance.
	 * @param array[string]float $predicateWeights
	 * @param int $costIns character insertion cost (defaults to 1)
	 * @param int $costRep character replacement cost (defaults to 1)
	 * @param int $costDel character deletion cost (defaults to 1)
	 */
	public function __construct($predicateWeights = array(), $costIns = 1, $costRep = 1, $costDel = 1)
	{
		$this->predicateWeights = $predicateWeights;
		$this->costIns = $costIns;
		$this->costRep = $costRep;
		$this->costDel = $costDel;
	}
	
	/**
	 * Compare two entities.
	 * @param entityresolution_Entity $queryEntity first entity
	 * @param entityresolution_Entity $blockEntity second entity
	 * @return double difference score, 0 is no difference, the greater the difference the greater the difference score
	 */
	public function compareEntities($queryEntity, $blockEntity)
	{
		//TODO: split in sub functions?
		
		// get the properties of both entities
		$queryEntityProperties = $queryEntity->getProperties();
		$blockEntityProperties = $blockEntity->getProperties();
		
		// track matched property predicates
		$queryEntityPropertyPredicates = array();
		// track matched property scores, each value has an array with the property value score indexed by the property value index number
		$queryEntityPropertyDifferenceScores = array();
		
		// loop over the query entity properties
		foreach($queryEntityProperties as $queryEntityPropertyIdx => $queryEntityProperty)
		{
			/* @var $queryEntityProperty entityresolution_Property */

			// property value scores indexed by the property value index number
			$queryEntityPropertyValueDifferenceScores = array();
			
			// loop over the query entity predicate forms
			$queryEntityPredicateForms = $queryEntityProperty->getPredicateForms();
			foreach($queryEntityPredicateForms as $queryEntityPredicateForm)
			{
				// loop over the block entity properties
				foreach($blockEntityProperties as $blockEntityProperty)
				{
					/* @var $blockEntityProperty entityresolution_Property */
					
					// see if any of the block entity properties matches the query entity property
					$blockEntityPredicateForms = $blockEntityProperty->getPredicateForms();
					if(in_array($queryEntityPredicateForm, $blockEntityPredicateForms))
					{
						// property match found
						
						// get the values for both entity properties
						$queryEntityPropertyValues = $queryEntityProperty->getValues();
						$blockEntityPropertyValues = $blockEntityProperty->getValues();
						
						// loop over the query entity propery values
						foreach($queryEntityPropertyValues as $queryEntityPropertyValueIdx => $queryEntityPropertyValue)
						{
							/* @var $queryEntityPropertyValue entityresolution_Value */

							// get the query entity property value forms
							$queryEntityPropertyValueForms = $queryEntityPropertyValue->getValueForms();
							
							// loop over the query entity propery values
							foreach($blockEntityPropertyValues as $blockEntityPropertyValue)
							{
								/* @var $blockEntityPropertyValue entityresolution_Value */

								// get the block entity property value forms
								$blockEntityPropertyValueForms = $blockEntityPropertyValue->getValueForms();
								
								// loop over the query entity propery value forms
								foreach($queryEntityPropertyValueForms as $queryEntityPropertyValueForm)
								{
									// limit the query value form length to 255 (limit for levenshtein())
									$queryEntityPropertyValueForm = substr($queryEntityPropertyValueForm, 0, 255);

									// loop over the block entity propery value forms
									foreach($blockEntityPropertyValueForms as $blockEntityPropertyValueForm)
									{
										// limit the block value form length to 255 (limit for levenshtein()) 
										$blockEntityPropertyValueForm = substr($blockEntityPropertyValueForm, 0, 255);
										
										// calculate the levensthein difference of the value forms
										$ld = levenshtein($queryEntityPropertyValueForm, $blockEntityPropertyValueForm, $this->costIns, $this->costRep, $this->costDel);
										
										// store the lowest difference for this property value
										if($queryEntityPropertyValueDifferenceScores[$queryEntityPropertyValueIdx] !== null)
										{
											$queryEntityPropertyValueDifferenceScores[$queryEntityPropertyValueIdx] = min($ld, $queryEntityPropertyValueDifferenceScores[$queryEntityPropertyValueIdx]);
										}
										else
										{
											$queryEntityPropertyValueDifferenceScores[$queryEntityPropertyValueIdx] = $ld;
										}
									}
								}
							}
						}
					}
				}
			}
			
			// store the predicate
			$queryEntityPropertyPredicates[$queryEntityPropertyIdx] = $queryEntityProperty->getPredicate();
			
			// store the value scores
			$queryEntityPropertyDifferenceScores[$queryEntityPropertyIdx] = $queryEntityPropertyValueDifferenceScores;
		}
		
//		print_r($queryEntityPropertyPredicates);
//		print_r($queryEntityPropertyDifferenceScores);

		// calculate the average difference score
		$differenceScore = 0.0;
		$weightSum = 0;
		foreach($queryEntityPropertyDifferenceScores as $queryEntityPropertyIdx => $queryEntityPropertyValueDifferenceScores)
		{
			// property weights by predicate URI
			$predicate = $queryEntityPropertyPredicates[$queryEntityPropertyIdx];
			$weight = $this->predicateWeights[$predicate];
			if($weight === null)
			{
				$weight = 1.0;
			}
//			print $predicate . '=' . $weight . "\n";
			
			foreach($queryEntityPropertyValueDifferenceScores as $queryEntityPropertyValueDifferenceScore)
			{
				if($queryEntityPropertyValueDifferenceScore !== null)
				{
					$differenceScore += $queryEntityPropertyValueDifferenceScore * $weight;
					$weightSum += $weight;
				}
			}
		}
//		print $weightSum . "\n";
		
		if($weightSum > 0)
		{
			$differenceScore = $differenceScore / $weightSum;
		}
		else
		{
			// no matching properties were found, return a null instead
			$queryEntityPropertyValueDifferenceScore = null;
		}
		
//		print $differenceScore . "\n";
		
		return $differenceScore;
	}
}